import java.util.*;
import java.lang.System;

/**
 *This is the Driver class. It has the main method that creates a new linked list
 *and then calls the linear and binary search methods
 *     		
 */


public class Driver
{
/**
*	This is the main method, which initializes a linked list, then calls the 
*	createList method to fill the list.
*	@param	args from command line 
*/

	public static void main(String[] args)
	{
		int size;
	
		//initialize linkedList
		LinkedList linkedList;
	
		System.out.print("Size: ");
		
		//check for command-line argument
		if ( args.length > 0 )
      {
			size = Integer.parseInt(args[0]);
      }
      else
      {
			size = size();
      }
		linkedList = createList(size);
		
		java.util.LinkedList linkedListXC = createListXC(size);
		
		//call search methods
		linearSearch(linkedList);
		binarySearch(linkedList);
		
		binarySearchXC(linkedListXC);
		
	}	

/**
*	This is the method that accepts a size from the user, if no command-line 
*	argument is given
*	@return	int size
*/
	
	public static int size()
	{
		Scanner kb = new Scanner(System.in);
		int size;
		while (true)
		{
			try
			{
				size = kb.nextInt();
				if(size < 0)
					throw new Exception();
				break;
			}
			catch (Exception e)
			{
				System.out.println("Invalid size type. Try again");
				kb.nextLine();
			}
		}
		System.out.printf("\nList of size %d created\n", size);
		return size;
	}
	
	
/**
*	This is the method that creates a linked list and fills it with even numbers
*	@param	size of the list
*	@return	new LinkedList that is created
*/
	public static LinkedList createList(int size)
	{
		
		int tempSize = size;
		Comparable temp;
		int data = 2;
		LinkedList linkedList = new LinkedList(); // contains dummy header
		while(tempSize > 0)
		{
			temp = new MyComparable((Integer)data);
			linkedList.add(temp);
			data = data + 2; 
			tempSize--;
		}
		return linkedList;
	}
	
/**
*	This class drives the linear search method in the LinkedList class. It searches
*	For all possible successful searches, and also for unsuccessful searches from
*	1 through (2*size + 1). No value is returned.
*	@param linkedList to search
*/
	public static void linearSearch(LinkedList linkedList)
	{
		System.out.println("\nLinear search: ");
		Comparable result;
		double startTime, stopTime, elapsedTime, averageTime;
		long count;
		
		//start time
		startTime = System.nanoTime();
		
		// search for all even numbers from 2 through (2*size)
		for(int i = 1; i <= linkedList.size(); i++)
		{		
			MyComparable tempSize = new MyComparable(i * 2);
			result = linkedList.linearSearch(tempSize);	
			if( result == null)
				System.out.println("Error: Could not find " + (i * 2));
		}
		
		//stop time
		stopTime = System.nanoTime();
		elapsedTime = stopTime - startTime;
		averageTime = elapsedTime / linkedList.size() * .001;//1 nanosecond == .001 microseconds
		
		count = MyComparable.nCompares() / linkedList.size();
		
		System.out.printf("%1.3f microseconds to find, %d comparisons\n", 
			averageTime, count);


		//start time
		startTime = System.nanoTime();
		//search for all odd numbers from 1 through (2*size + 1)
		for(int i = 0; i <= linkedList.size(); i++)
		{
			MyComparable tempSize = new MyComparable(i * 2 + 1);
			result = (Integer)linkedList.linearSearch(tempSize);
			if( result != null)
				System.out.println("Error: Should not have found " + (i * 2 + 1));
		}
		//stop time
		stopTime = System.nanoTime();
		
		elapsedTime = stopTime - startTime;
		averageTime = elapsedTime / (linkedList.size()+1) * .001;//1 nanosecond == .001 microseconds
		
		count = MyComparable.nCompares() / linkedList.size();
		
		System.out.printf("%1.3f microseconds to fail, %d comparisons\n\n", 
			averageTime, count);
		
	}
	
	//Binary Search=======================
/**
*	This is the binary search method. It calls the the binary search method
*	in the LinkedList class, then checks to be sure the expected results were
*	recieved.
*	@param	linkedList to search through
*/
	public static void binarySearch(LinkedList linkedList)
	{
		System.out.println("Binary Search:");
		Comparable result;
		double startTime, stopTime, elapsedTime, averageTime;
		long count;
		
		//start time
		startTime = System.nanoTime();
		// search for all even numbers from 2 through (2*size)
		for(int i = 1; i <= linkedList.size(); i++)
		{		
			MyComparable tempSize = new MyComparable(i * 2);
			result = linkedList.binarySearch(tempSize);	
			if( result == null)
				System.out.println("Error: Could not find " + (i * 2));
		}
		//stop time
		stopTime = System.nanoTime();
		
		elapsedTime = stopTime - startTime;
		averageTime = elapsedTime / linkedList.size() * .001;//1 nanosecond == .001 microseconds
	
		count = MyComparable.nCompares() / linkedList.size();
	
		System.out.printf("%1.3f microseconds to find, %d comparisons\n", 
			averageTime, count);


		//start time
		startTime = System.nanoTime();
		//search for all odd numbers from 1 through (2*size + 1)
		for(int i = 0; i <= linkedList.size(); i++)
		{
			MyComparable tempSize = new MyComparable(i * 2 + 1);
			result = linkedList.binarySearch(tempSize);
			if( result != null)
				System.out.println("Error: Should not have found " + (i * 2 + 1));
		}
		//stop time
		stopTime = System.nanoTime();
		
		elapsedTime = stopTime - startTime;
		averageTime = elapsedTime / (linkedList.size()+1) * .001;//1 nanosecond == .001 microseconds
		
		count = MyComparable.nCompares() / linkedList.size();
		
		System.out.printf("%1.3f microseconds to fail, %d comparisons\n\n", 
			averageTime, count);
		
	}
	
/**
*	This is the class that creates a linked list from java.util. It returns the
*	linkedList created.
*
*	@param size
*	@return LinkedList from java.util
*/
	public static java.util.LinkedList createListXC(int size)
	{
		int tempSize = size;
		Comparable temp;
		int data = 2;
		java.util.LinkedList linkedList = new java.util.LinkedList(); 
		while(tempSize > 0)
		{
			temp = new MyComparable((Integer)data);
			linkedList.add(temp);
			data = data + 2; 
			tempSize--;
		}
		return linkedList;
	}
	
/**
*	This is the binary search method that calls the binary search method of 
*	java.util.Collections.binarySearch(). It does the same basic steps as the 
*	normal binarySearch method. This biggest differences are that it accepts a 
*	parameter of java.util's linked list, instead of my created one, and the
*	java.util's binary search method returns a negative number if it couldn't 
*	find it, instead of a null reference pointer. 
*
*	@param linkedList from java.util
*/
	public static void binarySearchXC(java.util.LinkedList linkedList)
	{
		System.out.println("Binary Search using java.util:");
		Integer result;
		double startTime, stopTime, elapsedTime, averageTime;
		long count;
		
		//start time
		startTime = System.nanoTime();
		// search for all even numbers from 2 through (2*size)
		for(int i = 1; i <= linkedList.size(); i++)
		{		
			MyComparable tempSize = new MyComparable(i * 2);
			result = java.util.Collections.binarySearch(linkedList, tempSize);	
			if( result < 0)
				System.out.println("Error: Could not find " + (i * 2));
		}
		//stop time
		stopTime = System.nanoTime();
		
		elapsedTime = stopTime - startTime;
		averageTime = elapsedTime / linkedList.size() * .001;//1 nanosecond == .001 microseconds
	
		count = MyComparable.nCompares() / linkedList.size();
	
		System.out.printf("%1.3f microseconds to find, %d comparisons\n", 
			averageTime, count);


		//start time
		startTime = System.nanoTime();
		//search for all odd numbers from 1 through (2*size + 1)
		for(int i = 0; i <= linkedList.size(); i++)
		{
			MyComparable tempSize = new MyComparable(i * 2 + 1);
			result = java.util.Collections.binarySearch(linkedList, tempSize);
			if( result >= 0 )
				System.out.println("Error: Should not have found " + (i * 2 + 1));
		}
		//stop time
		stopTime = System.nanoTime();
		
		elapsedTime = stopTime - startTime;
		averageTime = elapsedTime / (linkedList.size()+1) * .001;//1 nanosecond == .001 microseconds
		
		count = MyComparable.nCompares() / linkedList.size();
		
		System.out.printf("%1.3f microseconds to fail, %d comparisons\n\n", 
			averageTime, count);
		

	}
	
	
}